#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    // 91. 解码方法
    // https://leetcode.cn/problems/decode-ways/
    int numDecodings(string s) {
        int n = s.size();
        if (n <= 1)
        {
            if ('1' <= s[0] && s[0] <= '9') return 1;
            else return 0;
        }

        vector<int> dp(n);
        int a = 0, b = 0;
        
        dp[0] = s[0] != '0';
        if (s[0]!='0' && s[1] != '0')
            dp[1] += 1;

        int num = (s[0]-'0')*10 + s[1]-'0';
        if ( 10 <= num && num <= 26 ) 
            dp[1] += 1;
        
        for (int i = 2; i<n; ++i)
        {
            if (s[i] != '0') dp[i] = dp[i-1];

            num = (s[i-1]-'0')*10 + s[i]-'0';
            if ( 10 <= num && num <= 26 ) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
    // 优化
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[1] = s[0] != '0';
        if (n <= 1) return dp[n];
        int num = 0;
        
        for (int i = 2; i<=n; ++i)
        {
            if (s[i-1] != '0') dp[i] = dp[i-1];
            num = (s[i-2]-'0')*10 + s[i-1]-'0';
            if ( 10 <= num && num <= 26 ) dp[i] += dp[i-2];
        }
        return dp[n];
    }

    // 62. 不同路径
    // https://leetcode.cn/problems/unique-paths/
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        dp[0][1] = 1;

        for (int i = 1; i<=m; ++i)
        {
            for (int j = 1; j<=n; ++j)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};